home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 March / macformat-022.iso / Shareware City / Developers / src / out-of-phase-102-c / OutOfPhase 1.02 Source / OutOfPhase Folder / SymbolTable.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-23  |  8.3 KB  |  277 lines  |  [TEXT/KAHL]
  1. /* SymbolTable.c */
  2. /*****************************************************************************/
  3. /*                                                                           */
  4. /*    Out Of Phase:  Digital Music Synthesis on General Purpose Computers    */
  5. /*    Copyright (C) 1994  Thomas R. Lawrence                                 */
  6. /*                                                                           */
  7. /*    This program is free software; you can redistribute it and/or modify   */
  8. /*    it under the terms of the GNU General Public License as published by   */
  9. /*    the Free Software Foundation; either version 2 of the License, or      */
  10. /*    (at your option) any later version.                                    */
  11. /*                                                                           */
  12. /*    This program is distributed in the hope that it will be useful,        */
  13. /*    but WITHOUT ANY WARRANTY; without even the implied warranty of         */
  14. /*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          */
  15. /*    GNU General Public License for more details.                           */
  16. /*                                                                           */
  17. /*    You should have received a copy of the GNU General Public License      */
  18. /*    along with this program; if not, write to the Free Software            */
  19. /*    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.              */
  20. /*                                                                           */
  21. /*    Thomas R. Lawrence can be reached at tomlaw@world.std.com.             */
  22. /*                                                                           */
  23. /*****************************************************************************/
  24.  
  25. #include "MiscInfo.h"
  26. #include "Audit.h"
  27. #include "Debug.h"
  28. #include "Definitions.h"
  29.  
  30. #include "SymbolTable.h"
  31. #include "SymbolTableEntry.h"
  32. #include "TrashTracker.h"
  33. #include "Memory.h"
  34. #include "DataMunging.h"
  35.  
  36.  
  37. /* since we use bit masking, the hash table size must be a power of 2 */
  38. #define HASHTABLESIZE (1L << 10)
  39. #define HASHTABLEMASK (HASHTABLESIZE - 1)
  40.  
  41.  
  42. typedef struct SymbolHeadRec
  43.     {
  44.         long                                        LexicalLevel;
  45.         struct SymbolHeadRec**    PreviousMetaAddress;
  46.         struct SymbolHeadRec*        Next; /* hash bucket link; also used on free list */
  47.         SymbolRec*                            Symbol;
  48.         struct SymbolHeadRec*        LexicalLevelNext;
  49.     } SymbolHeadRec;
  50.  
  51.  
  52. typedef struct LevelRec
  53.     {
  54.         struct LevelRec*                OneScopeDown; /* also used on free list */
  55.         SymbolHeadRec*                    ThisLevelList;
  56.     } LevelRec;
  57.  
  58.  
  59. struct SymbolTableRec
  60.     {
  61.         long                                LexicalLevel;
  62.         LevelRec*                        LevelStack;
  63.         TrashTrackRec*            Allocator;
  64.  
  65.         LevelRec*                        FreeLevelList;
  66.         SymbolHeadRec*            FreeSymbolHeadList;
  67.  
  68.         SymbolHeadRec*            HashTable[HASHTABLESIZE];
  69.     };
  70.  
  71.  
  72. /* create a new symbol table */
  73. SymbolTableRec*            NewSymbolTable(struct TrashTrackRec* TrashTracker)
  74.     {
  75.         SymbolTableRec*        SymbolTable;
  76.         long                            Scan;
  77.  
  78.         SymbolTable = (SymbolTableRec*)AllocTrackedBlock(sizeof(SymbolTableRec),TrashTracker);
  79.         if (SymbolTable == NIL)
  80.             {
  81.                 return NIL;
  82.             }
  83.         SetTag(SymbolTable,"SymbolTableRec");
  84.  
  85.         for (Scan = 0; Scan < HASHTABLESIZE; Scan += 1)
  86.             {
  87.                 SymbolTable->HashTable[Scan] = NIL;
  88.             }
  89.  
  90.         SymbolTable->FreeLevelList = NIL;
  91.         SymbolTable->FreeSymbolHeadList = NIL;
  92.  
  93.         SymbolTable->LexicalLevel = 0;
  94.         SymbolTable->Allocator = TrashTracker;
  95.  
  96.         SymbolTable->LevelStack = (LevelRec*)AllocTrackedBlock(sizeof(LevelRec),TrashTracker);
  97.         if (SymbolTable->LevelStack == NIL)
  98.             {
  99.                 return NIL;
  100.             }
  101.         SetTag(SymbolTable->LevelStack,"SymbolTableRec:  LevelStackRec");
  102.  
  103.         SymbolTable->LevelStack->OneScopeDown = NIL;
  104.         SymbolTable->LevelStack->ThisLevelList = NIL;
  105.  
  106.         return SymbolTable;
  107.     }
  108.  
  109.  
  110. /* create a new symbol table level */
  111. MyBoolean                        IncrementSymbolTableLevel(SymbolTableRec* SymbolTable)
  112.     {
  113.         LevelRec*                    NewLevel;
  114.  
  115.         CheckPtrExistence(SymbolTable);
  116.  
  117.         if (SymbolTable->FreeLevelList != NIL)
  118.             {
  119.                 NewLevel = SymbolTable->FreeLevelList;
  120.                 SymbolTable->FreeLevelList = SymbolTable->FreeLevelList->OneScopeDown;
  121.             }
  122.          else
  123.             {
  124.                 NewLevel = (LevelRec*)AllocTrackedBlock(sizeof(LevelRec),SymbolTable->Allocator);
  125.                 if (NewLevel == NIL)
  126.                     {
  127.                         return False;
  128.                     }
  129.             }
  130.  
  131.         NewLevel->OneScopeDown = SymbolTable->LevelStack;
  132.         NewLevel->ThisLevelList = NIL;
  133.  
  134.         SymbolTable->LevelStack = NewLevel;
  135.         SymbolTable->LexicalLevel += 1;
  136.  
  137.         return True;
  138.     }
  139.  
  140.  
  141. /* drop the current symbol table lexical level */
  142. void                                DecrementSymbolTableLevel(SymbolTableRec* SymbolTable)
  143.     {
  144.         SymbolHeadRec*        Scan;
  145.  
  146.         CheckPtrExistence(SymbolTable);
  147.         ERROR(SymbolTable->LexicalLevel == 0,PRERR(ForceAbort,
  148.             "DecrementSymbolTableLevel:  at outer level -- can't drop"));
  149.  
  150.         /* this list has been built in the order symbols were added.  so when we delink */
  151.         /* them, it's in the reverse order.  by induction, each element being deleted */
  152.         /* is at the head of it's hash bucket.  this is why we can use the metapointer. */
  153.         Scan = SymbolTable->LevelStack->ThisLevelList;
  154.         while (Scan != NIL)
  155.             {
  156.                 SymbolHeadRec*        Temp;
  157.  
  158.                 /* save the first node we are dropping */
  159.                 Temp = Scan;
  160.  
  161.                 /* delete node from current level's list */
  162.                 Scan = Scan->LexicalLevelNext;
  163.  
  164.                 /* delink node from it's bucket */
  165.                 *(Temp->PreviousMetaAddress) = Temp->Next;
  166.  
  167.                 /* stick temp onto the free list */
  168.                 Temp->Next = SymbolTable->FreeSymbolHeadList;
  169.                 SymbolTable->FreeSymbolHeadList = Temp;
  170.             }
  171.  
  172.         /* drop the stack record */
  173.         SymbolTable->LevelStack = SymbolTable->LevelStack->OneScopeDown;
  174.     }
  175.  
  176.  
  177. /* add symbol table entry to the symbol table.  returns a result code */
  178. AddSymbolType                AddSymbolToTable(SymbolTableRec* SymbolTable,
  179.                                             struct SymbolRec* SymbolToAdd)
  180.     {
  181.         SymbolHeadRec*        SymbolHead;
  182.         long                            HashIndex;
  183.         char*                            SymbolName;
  184.  
  185.         CheckPtrExistence(SymbolTable);
  186.         CheckPtrExistence(SymbolToAdd);
  187.  
  188.         /* find out where in the hash table it belongs */
  189.         HashIndex = HASHTABLEMASK & GetSymbolHashValue(SymbolToAdd);
  190.  
  191.         /* see if symbol already exists */
  192.         SymbolName = GetSymbolName(SymbolToAdd);
  193.         CheckPtrExistence(SymbolName);
  194.         /* it must be at this level only */
  195.         SymbolHead = SymbolTable->HashTable[HashIndex];
  196.         while ((SymbolHead != NIL) && (SymbolHead->LexicalLevel == SymbolTable->LexicalLevel))
  197.             {
  198.                 char*                            OtherSymbolName;
  199.  
  200.                 OtherSymbolName = GetSymbolName(SymbolHead->Symbol);
  201.                 if (PtrSize(OtherSymbolName) == PtrSize(SymbolName))
  202.                     {
  203.                         if (MemEqu(OtherSymbolName,SymbolName,PtrSize(SymbolName)))
  204.                             {
  205.                                 return eAddSymbolAlreadyExists;
  206.                             }
  207.                     }
  208.                 SymbolHead = SymbolHead->Next;
  209.             }
  210.  
  211.         if (SymbolTable->FreeSymbolHeadList != NIL)
  212.             {
  213.                 SymbolHead = SymbolTable->FreeSymbolHeadList;
  214.                 SymbolTable->FreeSymbolHeadList = SymbolTable->FreeSymbolHeadList->Next;
  215.             }
  216.          else
  217.             {
  218.                 SymbolHead = (SymbolHeadRec*)AllocTrackedBlock(sizeof(SymbolHeadRec),
  219.                     SymbolTable->Allocator);
  220.                 if (SymbolHead == NIL)
  221.                     {
  222.                         return eAddSymbolNoMemory;
  223.                     }
  224.                 SetTag(SymbolHead,"SymbolHeadRec");
  225.             }
  226.  
  227.         /* set the meta reference for delinking */
  228.         SymbolHead->PreviousMetaAddress = &(SymbolTable->HashTable[HashIndex]);
  229.  
  230.         /* add the thing to the hash chain (at the head) */
  231.         SymbolHead->Next = SymbolTable->HashTable[HashIndex];
  232.         SymbolTable->HashTable[HashIndex] = SymbolHead;
  233.  
  234.         /* put the symbol in the record */
  235.         SymbolHead->Symbol = SymbolToAdd;
  236.  
  237.         /* link it into the lexical level thing */
  238.         SymbolHead->LexicalLevelNext = SymbolTable->LevelStack->ThisLevelList;
  239.         SymbolTable->LevelStack->ThisLevelList = SymbolHead;
  240.  
  241.         /* set the lexical level */
  242.         SymbolHead->LexicalLevel = SymbolTable->LexicalLevel;
  243.  
  244.         return eAddSymbolNoErr;
  245.     }
  246.  
  247.  
  248. /* get a symbol from the symboldflksakdo table */
  249. /* it returns NIL if the entry was not found. */
  250. struct SymbolRec*        GetSymbolFromTable(SymbolTableRec* SymbolTable, char* NameString,
  251.                                             long NameStringLength)
  252.     {
  253.         SymbolHeadRec*        SymbolHead;
  254.  
  255.         CheckPtrExistence(SymbolTable);
  256.  
  257.         SymbolHead = SymbolTable->HashTable[HASHTABLEMASK
  258.             & UseSymbolTableHash(NameString,NameStringLength)];
  259.         while (SymbolHead != NIL)
  260.             {
  261.                 char*                            OtherSymbolName;
  262.  
  263.                 OtherSymbolName = GetSymbolName(SymbolHead->Symbol);
  264.                 if (PtrSize(OtherSymbolName) == NameStringLength)
  265.                     {
  266.                         if (MemEqu(OtherSymbolName,NameString,NameStringLength))
  267.                             {
  268.                                 /* found it! */
  269.                                 return SymbolHead->Symbol;
  270.                             }
  271.                     }
  272.                 SymbolHead = SymbolHead->Next;
  273.             }
  274.  
  275.         return NIL;
  276.     }
  277.